红黑树 (Red-Black Tree)

1. 定义:

   • 红黑树是一种自平衡的二叉查找树（Self-Balancing Binary Search Tree）。
   • 它在普通的二叉查找树基础上，为每个节点增加了一个颜色属性（红色或黑色）。
   • 通过一系列着色和旋转规则来维持树的平衡，确保从根到最远叶子节点的路径长度不会超过到最近叶子节点路径长度的两倍，从而保证了操作的最坏时间复杂度为 O(log N)。

2. 核心性质 (必须满足):

   • 性质 1: 每个节点要么是红色，要么是黑色。
   • 性质 2: 根节点必须是黑色。
   • 性质 3: 所有叶子节点（NIL 节点，空节点，通常视为外部节点）都是黑色的。
   • 性质 4: 如果一个节点是红色的，那么它的两个子节点必须是黑色的。（不能有两个连续的红色节点）。
   • 性质 5: 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（称为“黑高”，Black-Height）。

3. 平衡维护:

   • 当插入或删除节点时，可能会破坏上述性质。
   • 通过两种主要操作来恢复平衡：
     • 重新着色 (Recoloring): 改变某些节点的颜色。
     • 旋转 (Rotation): 左旋或右旋，改变树的局部结构，同时保持二叉查找树的性质。
   • 这些操作组合起来，可以在 O(log N) 时间内完成插入和删除，并重新满足红黑树的性质。

4. 优点:

   • 最坏情况性能保证: 查找、插入、删除操作的最坏时间复杂度都是 O(log N)。这是它相比普通二叉查找树（最坏 O(N)）的主要优势。
   • 相对高效的插入/删除: 相较于其他严格平衡的树（如 AVL 树），红黑树在插入和删除时需要的旋转次数相对较少，因此在写操作频繁的场景下可能效率更高一些。

5. 缺点:

   • 实现复杂: 红黑树的插入和删除逻辑，特别是平衡调整部分，涉及多种情况，实现起来比较复杂且容易出错。
   • 查找效率略低于AVL树: 因为它的平衡性没有 AVL 树那么严格，树的高度可能略高一点，导致查找的常数因子可能稍大。

6. 应用:

   • 广泛用于需要高效有序存储和检索的场景。
   • C++ STL 中的 std::map, std::set, std::multimap, std::multiset。
   • Java 中的 java.util.TreeMap, java.util.TreeSet。
   • Linux 内核中的 Completely Fair Scheduler (CFS) 进程调度。
   • 内存管理等。

跳表 (Skip List)

1. 定义:

   • 跳表是一种概率性 (Probabilistic) 数据结构，它使用多层链表来实现快速查找。
   • 可以看作是对有序链表的改进，通过添加额外的“快速通道”（上层链表）来跳过部分节点，从而加速查找过程。

2. 结构:

   • 底层 (Level 0): 是一个标准的有序链表，包含所有元素。
   • 上层 (Level 1, Level 2,…): 每一层都是下一层链表的一个子集。一个节点出现在第 i 层，那么它也必须出现在所有低于 i 的层（0 到 i-1 层）。
   • 每个节点包含：
     • 数据值 (key/value)。
     • 指向同一层下一个节点的指针 (forward 指针数组，每个索引对应一层)。
     • 节点的高度（它存在于多少层中）。

3. 工作原理:

   • 查找: 从最高层的头节点开始，向右查找，直到找到第一个大于或等于目标值的节点的前一个节点。然后下降到下一层，重复这个过程，直到到达最底层。最后在最底层链表中精确查找。

   • 插入:

     1. 先像查找一样找到插入位置。
     2. 随机决定新节点的层数 (高度)。通常使用抛硬币的方式，比如有 50% 概率提升一层，直到失败或达到最大层数。
     3. 在节点应该出现的每一层（从 0 到其随机决定的最高层）中，像普通链表一样插入该节点，并更新前后节点的指针。

   • 删除:

     1. 像查找一样找到要删除的节点（需要记录每一层路径上的前驱节点）。
     2. 在节点出现的每一层中，将其从链表中移除（更新前驱节点的 forward 指针）。

4. 平衡维护:

   • 跳表不依赖于旋转等复杂的确定性平衡操作。
   • 它的平衡性是通过概率来保证的。随机决定节点层数的策略使得高层链表节点数量指数级减少，结构上期望接近于一个平衡树。

5. 优点:

   • 实现相对简单: 相较于红黑树，跳表的插入和删除逻辑（主要是指针操作）更直观，没有复杂的旋转和着色规则。
   • 性能优秀: 期望时间复杂度为 O(log N)，实践中常数因子通常较小，性能可能优于红黑树，尤其是在并发环境下。
   • 易于实现并发: 跳表的结构天然适合细粒度锁或无锁（Lock-Free）的并发实现。

6. 缺点:

   • 概率性: 性能是期望 O(log N)，虽然概率极小，但存在性能退化到 O(N) 的可能性（如果随机层数生成得非常不均衡）。
   • 空间开销: 每个节点需要存储多个指针（平均约 2 个，取决于概率 P），比红黑树（通常 2-3 个指针加 1 位颜色）或普通链表（1 个指针）需要更多的内存空间。

7. 应用:

   • 数据库和缓存系统：Redis 的有序集合 (Sorted Set) 就是用跳表实现的。LevelDB 和 RocksDB 也使用跳表作为 MemTable 的数据结构。
   • 需要高性能、易于实现（尤其是并发）的有序映射或集合场景。

红黑树和AVL树有什么区别？

它们都是自平衡二叉查找树（Self-Balancing Binary Search Tree），旨在解决普通二叉查找树在最坏情况下可能退化成链表（导致 O(N) 操作复杂度）的问题，确保查找、插入和删除操作的时间复杂度维持在 O(log N)。

它们的主要区别在于平衡策略的严格程度以及由此带来的性能特点和实现复杂度。

1. 平衡策略和严格性:

   • AVL 树: 非常严格。它要求任何节点的左右子树高度差（称为平衡因子 Balance Factor）的绝对值不能超过 1 (即只能是 -1, 0, 1)。
   • 红黑树: 相对宽松。它通过 5 条红黑规则（涉及节点颜色和黑色节点数量）来间接维持平衡。它不直接限制左右子树的高度差，而是保证从根到最远叶子节点的最长路径不会超过到最近叶子节点的最短路径的两倍。

2. 树的高度:

   • AVL 树: 由于其严格的平衡条件，AVL 树的高度尽可能低，是所有自平衡二叉查找树中高度最接近理想平衡状态（完全二叉树）的。其高度 H 约为 1.44 * log₂(N)。
   • 红黑树: 平衡性要求较宽松，允许的高度范围更大一些。其高度 H 最多约为 2 * log₂(N+1)。通常比相同节点数的 AVL 树要高一点。

3. 查找性能:

   • AVL 树: 因为树的高度更低，查找操作需要遍历的节点数通常更少，所以查找效率通常略高于红黑树。
   • 红黑树: 树可能稍高，查找效率可能略低于 AVL 树，但仍然是 O(log N) 级别。

4. 插入和删除性能 (平衡调整):

   • AVL 树: 为了维持严格的平衡因子限制，插入或删除节点后，可能需要进行多次旋转（最多 O(log N) 次，但通常较少）来恢复平衡。调整操作可能比较频繁且复杂（涉及单旋转和双旋转）。
   • 红黑树: 平衡调整主要通过重新着色 (Recoloring) 和旋转 (Rotation) 来完成。重新着色操作非常快 (O(1))。旋转操作在红黑树中发生的频率相对较低，并且插入最多需要 2 次旋转，删除最多需要 3 次旋转。因此，红黑树在插入和删除操作上的平均开销通常比 AVL 树要小。

5. 实现复杂度:

   • AVL 树: 实现相对复杂。需要存储每个节点的平衡因子（或子树高度），并且旋转逻辑（特别是双旋转）比红黑树稍微复杂一些。
   • 红黑树: 实现也非常复杂，涉及 5 条规则和多种情况的调整（旋转和着色）。虽然旋转次数少，但规则的判断和应用也需要仔细处理。两者实现难度都比较高，但有时认为红黑树的规则驱动方式可能比计算和维护平衡因子稍微直观一点（尽管调试起来都不容易）。

6. 空间复杂度:

   • AVL 树: 每个节点需要额外存储平衡因子（通常是一个小整数）或子树高度。
   • 红黑树: 每个节点只需要额外存储 1 bit 的颜色信息。如果需要父指针（很多实现都需要），两者空间开销相似。

红黑树是如何进行平衡的？

一、 插入操作后的平衡调整

1. 初始插入: 按照标准的二叉查找树（BST）规则找到插入位置，并将新节点 N 标记为 红色 (RED)。

   • 为什么是红色？ 如果插入黑色节点，几乎肯定会改变其所在路径的黑高（Black-Height），违反性质 5。插入红色节点，黑高不变，只会可能违反性质 2（根节点为黑）或性质 4（红色节点的子节点必须是黑色）。违反这两个性质相对容易修复。

2. 检查冲突:

   • 情况 1: 插入的是根节点: 直接将根节点颜色改为 黑色 (BLACK)。满足性质 2，其他性质自然满足。操作完成。
   • 情况 2: 新节点 N 的父节点 P 是黑色: 新插入的红色节点 N 没有违反任何性质。操作完成。
   • 情况 3: 新节点 N 的父节点 P 是红色: 这就违反了性质 4（不能有连续的红色节点）。此时需要进行调整。设 G 为祖父节点（P 的父节点，G 必定存在且为黑色，因为 P 是红色，根节点不能是红色，或者如果 P 是根，则情况 1 已处理），U 为叔叔节点（G 的另一个子节点）。

3. 修复冲突 (当父节点 P 是红色时):

   • 修复 Case 1: 叔叔 U 是红色:
     • 操作: 将父节点 P 和叔叔 U 都改为 黑色 (BLACK)。将祖父节点 G 改为 红色 (RED)。
     • 效果: 局部解决了 N 和 P 的双红问题。但是，祖父节点 G 变红，可能会与它的父节点产生新的双红问题。
     • 下一步: 将 G 视为新的 N，继续向上递归检查和调整。
   • 修复 Case 2: 叔叔 U 是黑色 (或 NIL 节点，视为黑色): 这种情况需要通过旋转和重新着色来解决，并且调整后树的平衡就恢复了，不需要再向上递归。这又分为两种子情况，取决于 N, P, G 的相对位置：
     • 子情况 2a: “外部情况” (Line Case): N 是 P 的外侧子节点 (例如, G -> P (左) -> N (左), 或者 G -> P (右) -> N (右))。
       • 操作: 将父节点 P 改为 黑色 (BLACK)。将祖父节点 G 改为 红色 (RED)。对祖父节点 G 进行一次单旋转 (LL 情况右旋 G，RR 情况左旋 G)。
       • 效果: 旋转后，原父节点 P 成为子树的新根，颜色变黑。原祖父 G 和新节点 N 成为 P 的子节点，颜色变红。双红问题解决，且子树黑高不变。
     • 子情况 2b: “内部情况” (Triangle Case): N 是 P 的内侧子节点 (例如, G -> P (左) -> N (右), 或者 G -> P (右) -> N (左))。
       • 操作: 先对父节点 P 进行一次单旋转 (LR 情况左旋 P，RL 情况右旋 P)，将内部情况转换为外部情况 (子情况 2a)。此时 N 成为了原来 P 的位置，原来的 P 成为了 N 的子节点。
       • 下一步: 将转换后的节点 N (现在扮演了新 P 的角色) 应用子情况 2a 的操作来完成调整。这通常涉及将 N 变黑，G 变红，再对 G 进行旋转。

二、 删除操作后的平衡调整

删除操作比插入更复杂，因为它可能同时违反性质 4 和性质 5。

1. 初始删除: 按照标准的 BST 删除规则执行。

   • 如果删除的节点 Z 有两个子节点，会找到其后继节点 Y (右子树的最左节点)，用 Y 的值替换 Z 的值，然后问题转化为删除节点 Y (它最多只有一个非 NIL 子节点)。
   • 所以，最终实际被物理删除的节点 (Z 或 Y) 最多只有一个非 NIL 子节点。令 X 为实际顶替被删除节点位置的那个节点（可能是其唯一的子节点，或者 NIL 节点）。

2. 判断是否需要调整:

   • 如果被删除的节点 (Z 或 Y) 是红色: 删除它不会影响任何路径的黑高，也不会产生两个相邻的红色节点（因为它的父节点和子节点（如果存在）必定是黑色）。无需调整。
   • 如果被删除的节点是黑色: 这会减少其所有祖先路径上的黑高，违反性质 5。需要进行调整。我们认为节点 X（顶替者）现在具有“双重黑色” (double black) 或“缺少黑色” (missing black) 的属性，需要修复。

3. 修复冲突 (当删除的是黑色节点时):

   • 调整过程是一个循环，从 X 开始，不断向上移动，直到“双重黑色”被解决，或者到达根节点。设 P 为 X 的父节点，W 为 X 的兄弟节点。
   • 调整循环: 只要 X 不是根节点且 X 是“双重黑色”，就执行以下情况判断：
     • 修复 Case 1: 兄弟 W 是红色:
       • 操作: 将 W 改为 黑色 (BLACK)。将父节点 P 改为 红色 (RED)。对父节点 P 进行一次旋转 (将 W 旋上来)。
       • 效果: 旋转后，X 有了一个新的黑色兄弟 (原 W 的某个子节点)。这并未解决双重黑色，但将问题转化为兄弟 W 是黑色的情况 (Case 2, 3, 或 4)。
     • 修复 Case 2: 兄弟 W 是黑色，且 W 的两个子节点都是黑色:
       • 操作: 将 W 改为 红色 (RED)。如果 P 是 红色 (RED)，那么出现双红，此时将 P 改为 黑色 (BLACK)，完成平衡，否则传递双黑节点到 P
       • 效果: 将 X 和 W 子树的“缺少黑色”问题传递给了父节点 P。P 现在成为了新的“双重黑色”节点。
       • 下一步: 令 X = P，继续下一轮循环。
     • 修复 Case 3: 兄弟 W 是黑色，W 的靠近 X 一侧的子节点是红色，远离 X 一侧的子节点是黑色: (Triangle Case)
       • 操作: 将 W 的红色子节点改为 黑色 (BLACK)。将 W 改为 红色 (RED)。对 W 进行一次旋转 (将红色子节点 （此时被染成黑色了） 旋上来)。
       • 效果: 旋转后，X 有了一个新的黑色兄弟 (原 W 的红色子节点)，且这个新兄弟有一个红色的远侧子节点（被染成红色的W）。这并未解决双重黑色，但将问题转化为 Case 4。
     • 修复 Case 4: 兄弟 W 是黑色，且 W 的远离 X 一侧的子节点是红色: (Line Case)
       • 操作: 将 W 的颜色改为 P 的颜色。将 P 的颜色改为 黑色 (BLACK)。将 W 的红色远侧子节点改为 黑色 (BLACK)。对父节点 P 进行一次旋转 (将 W 旋上来)。
       • 效果: 彻底解决了 X 的“双重黑色”问题。旋转和重新着色恢复了子树的黑高。
       • 下一步: 平衡完成。可以终止循环。

4. 循环终止: 当 X 成为了根节点，或者“双重黑色”通过 Case 4 或者 Case 2 被解决时，循环停止。如果 X 是根节点，它吸收了“双重黑色”，保持黑色即可。

B 树 (B-Tree)

1. 定义与目的:

   • B 树是一种自平衡的树状数据结构，能够保持数据有序，并允许在 O(log N) 时间内进行搜索、顺序访问、插入和删除。
   • 它是一种多路查找树，意味着每个节点可以有多个子节点（超过 2 个）。
   • 主要用于数据库和文件系统中，以减少磁盘访问次数。

2. 核心特性:

   • 数据存储: 关键字 (Keys) 和 数据 (Data)（或指向数据的指针）都存储在内部节点和叶子节点中。找到关键字就可能直接找到了对应的数据（或其指针）。
   • 节点结构: 每个节点包含：
     • 若干个关键字 (Keys)，按升序排列。
     • 如果存储的是数据指针，则每个关键字关联一个数据指针。
     • 指向子节点的指针 (Child Pointers)。一个有 k 个关键字的节点通常有 k+1 个子节点指针。关键字 Key_i 用于分隔子指针 P_i 和 P_{i+1} 所指向的子树中的关键字范围。
   • 平衡性: 所有叶子节点都处于同一层级。
   • 阶数 (Order) m: 定义了节点容量。一个 m 阶 B 树满足：
     • 每个节点最多包含 m-1 个关键字和 m 个子指针。
     • 除根节点外，每个非叶子节点至少有 ceil(m/2) - 1 个关键字和 ceil(m/2) 个子指针。（ceil 是向上取整）。
     • 根节点如果不是叶子节点，则至少有 1 个关键字和 2 个子指针。
     • 节点内的关键字数量决定了其子节点的数量。

3. 操作:

   • 查找: 从根节点开始，在节点内部使用二分查找（或线性查找，因为节点内关键字不多）找到合适的关键字范围，然后沿着对应的子指针向下递归查找，直到找到关键字或到达叶子节点。如果在内部节点找到关键字，就可能直接获取数据。

   • 插入: 先查找到合适的叶子节点进行插入。

     • 如果叶子节点有空间，直接插入。

     • 如果叶子节点已满 (达到 m-1 个关键字)，则需要分裂 (Split)：

       1. 将新关键字加入节点，使其暂时包含 m 个关键字。
       2. 选取中间的关键字。
       3. 将节点分裂成两个新节点，分别包含中间关键字左侧和右侧的关键字。
       4. 将中间关键字提升 (Promote) 到父节点中。
       5. 如果父节点也满了，则递归向上分裂。如果分裂一直传播到根节点，树的高度会增加 1。

   • 删除: 稍微复杂。

     • 先查找到包含关键字的节点。

     • Case 1: 关键字在叶子节点: 直接删除。如果删除后节点关键字数量低于下限 (ceil(m/2) - 1)，则需要平衡调整:

       • 旋转/借用 (Rotation/Borrow): 如果相邻兄弟节点有多余关键字，可以从兄弟节点“借”一个关键字过来，通过父节点进行调整。
       • 合并 (Merge): 如果兄弟节点也没有多余关键字（刚好满足下限），则将该节点与其一个兄弟节点以及父节点中分隔它们的关键字合并成一个新节点。合并可能导致父节点关键字减少，需要递归向上进行平衡调整。

     • Case 2: 关键字在内部节点:

       1. 找到该关键字的前驱 (predecessor) 或 后继 (successor) 关键字（它们必定位于叶子节点）。
       2. 用前驱或后继关键字替换要删除的内部节点关键字。
       3. 现在问题转化为删除叶子节点中的前驱/后继关键字，按 Case 1 处理。

4. 优点:

   • 平衡性保证了 O(log N) 的操作复杂度。
   • 多路特性降低了树的高度，大大减少了磁盘 I/O。
   • 点查询（查找特定关键字）可能在到达叶子节点前就在内部节点结束，可能更快。

5. 缺点:

   • 范围查询 (Range Query) 效率相对较低。因为数据分散在内部节点和叶子节点，执行范围查询可能需要频繁地在树的不同层级之间移动（中序遍历）。
   • 插入和删除操作可能引起节点的分裂和合并，实现相对复杂。
   • 内部节点存储数据指针（或数据本身），使得每个节点能容纳的关键字数量相对较少（相比 B+ 树），可能导致树的高度略高。

B+ 树 (B+Tree)

B+ 树是 B 树的一种变体，针对数据库索引等场景做了优化。

1. 定义与目的:

   • B+ 树也是一种平衡多路查找树，用于高效的磁盘数据组织。
   • 它在 B 树的基础上做了修改，特别优化了范围查询和顺序访问的性能。

2. 核心特性:

   • 数据存储:
     • 内部节点: 只存储关键字 (Keys)，不存储数据（或数据指针）。这些关键字仅作为索引（路标），用于导航查找路径。
     • 叶子节点: 存储了所有的关键字以及对应的数据（或数据指针）。所有数据记录都只存在于叶子层。
   • 叶子节点链接: 所有叶子节点通过指针链接在一起，形成一个有序链表。这极大地提高了范围查询和顺序遍历的效率。
   • 冗余关键字: 内部节点中的关键字可能在叶子节点中重复出现 (作为该子树范围的下界或上界)。
   • 节点结构:
     • 内部节点: 结构类似 B 树，但只有关键字和子节点指针 [P0, K1, P1, K2, P2,…, Kn, Pn]。
     • 叶子节点: 包含关键字、数据（或数据指针）以及指向下一个叶子节点的指针 [(K1, Data1), (K2, Data2),…, (Kx, Datax), NextLeafPtr]。
   • 平衡性: 所有叶子节点都在同一层级。
   • 阶数 (Order) m: 定义与 B 树类似。但由于内部节点不存数据，对于相同大小的磁盘块（节点大小），B+ 树的内部节点可以容纳更多的关键字，因此分支因子 (fanout) 通常比 B 树更大，导致树的高度更低。

3. 操作:

   • 查找: 所有查找最终都必须到达叶子节点才能获取数据。内部节点仅用于导航。查找过程与 B 树类似，但即使在内部节点找到匹配的关键字，也需要继续沿着指针向下走，直到叶子节点。
   • 插入:
     1. 找到合适的叶子节点插入 (Key, Data)。
     2. 如果叶子节点有空间，直接插入。
     3. 如果叶子节点已满，则分裂:
        • 将节点（包含新项）分裂成两个叶子节点。
        • 将中间关键字（或新右侧节点的第一个关键字）复制 (Copy) 到父节点中作为新的分隔符。注意是复制，该关键字仍在叶子节点中。
        • 更新叶子节点的链表指针。
        • 如果父节点也满了，递归向上分裂内部节点（提升关键字，而不是复制）。
   • 删除:
     1. 找到包含该关键字的叶子节点并删除 (Key, Data)。
     2. 如果删除后叶子节点关键字数量低于下限，执行平衡调整（旋转/借用或合并叶子节点，并更新链表指针）。
     3. 合并/借用时需要更新父节点中的关键字。如果合并导致父节点关键字减少，可能需要递归向上调整内部节点。
     4. 注意：即使删除了叶子节点中的关键字，该关键字如果存在于内部节点作为索引，通常不需要立即删除，它仍然可以作为有效的路径分隔符。只有在合并导致子树结构变化，使得该索引关键字不再有效时才需要调整或删除。

4. 优点:

   • 更高的分支因子 (Fanout): 内部节点不存数据，可以放更多关键字，树更矮，磁盘 I/O 更少。
   • 极高的范围查询效率: 找到范围起点后，只需沿着叶子节点的链表顺序遍历即可，无需回溯树。
   • 稳定的查询性能: 所有查询最终都落到叶子节点，查询路径长度相对稳定。
   • 更适合数据库索引: 数据库索引通常需要高效的范围扫描和精确查找。

5. 缺点:

   • 点查询可能略慢: 因为所有查询都必须走到叶子节点。
   • 内部节点存在冗余关键字。

B树 和 B+树 有什么区别？

总结: B+ 树通过牺牲内部节点的存储空间（不存数据），换来了更大的分支因子（更矮的树）和高效的范围查询能力（叶子链表），这使其成为现代数据库索引结构的事实标准。B 树则相对更通用一些，但在需要大量范围查询的场景下不如 B+ 树。

红黑树和B/B+树有什么区别？

最核心的区别在于：

• 红黑树: 主要设计用于 内存中 的数据结构，目标是提供高效的（O(log N) 时间复杂度）动态查找、插入、删除操作，是一种二叉查找树。
• B/B+ 树: 主要设计用于 磁盘或其他块存储设备 上的数据结构（如数据库索引、文件系统），核心目标是最小化磁盘 I/O 操作次数，是一种多路查找树。

以下是详细的对比：

1. 结构类型:

   • 红黑树: 是 二叉 (Binary) 查找树。每个节点最多有 2 个子节点。
   • B/B+ 树: 是 多路 (Multiway) 查找树。每个节点可以包含多个关键字，并拥有多个（远超 2 个）子节点。这个“多路”特性是其减少磁盘 I/O 的关键。

2. 设计目标与优化方向:

   • 红黑树: 优化 CPU 计算时间，保证操作在对数时间内完成。它假设内存访问速度相对均匀且快速。
   • B/B+ 树: 优化 磁盘 I/O 次数。磁盘读写非常慢，B/B+ 树通过让每个节点存储更多信息（关键字和指针）并拥有更多分支（高扇出/阶数 Fanout/Order），使得树的高度大大降低。这样，从根节点到叶子节点需要读取的磁盘块数量就显著减少了。

3. 节点容量与树高:

   • 红黑树: 每个节点只存储 1 个关键字和相关数据。树的高度约为 O(log₂ N)。
   • B/B+ 树: 每个节点可以存储多个关键字（通常远多于 1 个，数量在一个范围内 [ceil(m/2)-1, m-1]，m 是树的阶数）。由于扇出 m 很大（可以达到几百甚至上千），树的高度非常低，约为 O(log_m N)。对于非常大的 N，树的高度通常只有 3-5 层。

4. 数据存储位置:

   • 红黑树: 数据（或指向数据的指针）与关键字一起存储在所有节点中。
   • B 树: 数据（或指向数据的指针）与关键字一起存储在内部节点和叶子节点中。
   • B+ 树: 数据（或指向数据的指针）只存储在叶子节点中。内部节点仅存储关键字作为索引（路标）。

5. 查找方式:

   • 红黑树: 标准的二叉树查找，比较后向左或向右。
   • B/B+ 树: 在节点内部进行查找（通常是二分或顺序查找）确定范围，然后沿着对应的子节点指针向下查找。
     • B 树: 查找到关键字可能在内部节点就结束了。
     • B+ 树: 所有查找最终都必须到达叶子节点才能获取数据。

6. 范围查询效率:

   • 红黑树: 范围查询需要进行中序遍历，效率相对较低，可能需要在树的不同层级间移动。
   • B 树: 范围查询也类似中序遍历，效率不高。
   • B+ 树: 范围查询效率极高。因为所有数据都在叶子节点，并且叶子节点之间通过指针形成了有序链表。找到范围起点后，只需沿着叶子链表顺序扫描即可，无需回溯树结构，磁盘访问非常连续。

7. 插入与删除:

   • 红黑树: 通过旋转和重新着色来维持平衡。操作相对复杂，但影响范围通常是局部的。
   • B/B+ 树: 通过节点分裂和节点合并/借调来维持平衡。当节点满时分裂，当节点关键字过少时合并或从兄弟节点借调。这些操作可能向上层传播。

8. 应用场景:

   • 红黑树:
     • 内存中的数据结构：C++ STL (map, set), Java (TreeMap, TreeSet)。
     • 进程调度：Linux 内核的 CFS 调度器。
     • 其他需要高效动态有序集合的内存场景。
   • B/B+ 树:
     • 数据库索引: 几乎所有关系型数据库都使用 B+ 树（或其变种）作为主要的索引结构 (如 MySQL InnoDB, PostgreSQL)。
     • 文件系统: 用于管理目录结构和文件块索引 (如 NTFS, HFS+, ext4 的 Htree 索引)。

堆

核心概念与特点:

1. 结构性:

   • 完全二叉树: 堆通常用完全二叉树来实现。这意味着树的所有层级都是满的，除了可能的最后一层，最后一层的节点都尽量靠左排列。
   • 数组表示: 由于完全二叉树的特性，堆非常适合用**数组（或列表/向量）**来高效地存储，无需使用指针。父节点和子节点之间的关系可以通过数组下标的计算直接得出：
     • 对于下标为 i 的节点 (假设从 0 开始计数):
       • 父节点下标: floor((i - 1) / 2)
       • 左子节点下标: 2 * i + 1
       • 右子节点下标: 2 * i + 2
     • (如果从 1 开始计数，则父节点是 floor(i / 2), 左子节点 2_i, 右子节点 2_i + 1)

2. 堆属性 (Heap Property):

   • 这是堆的核心规则，决定了节点值与其子节点值之间的关系。根据这个属性，堆分为两种主要类型：
     • 最大堆 (Max-Heap): 父节点的值 大于或等于 (>=) 其所有子节点的值。这意味着堆顶（根节点）存储的是整个堆中的最大值。
     • 最小堆 (Min-Heap): 父节点的值 小于或等于 (<=) 其所有子节点的值。这意味着堆顶（根节点）存储的是整个堆中的最小值。
   • 注意: 堆属性只规定了父子关系，兄弟节点之间没有确定的大小关系。所以堆不是完全排序的结构。

主要操作:

堆的核心价值在于能够高效地执行以下操作：

1. 插入 (Insert / Add):

   • 过程: 将新元素添加到堆的末尾（数组的末尾），以保持完全二叉树的结构。然后，将这个新元素与其父节点比较，如果违反了堆属性（例如，在最大堆中新元素比父节点大），则交换它们的位置。这个过程（称为上浮 sift-up / bubble-up / swim）持续进行，直到新元素到达正确的位置（不再违反堆属性）或到达堆顶。
   • 复杂度: O(log N)，因为最多需要沿着树的高度进行交换。

2. 删除堆顶元素 (Extract-Max / Extract-Min):

   • 过程: 堆顶元素（最大值或最小值）是最常被需要或删除的。

     1. 保存堆顶元素的值（用于返回）。
     2. 将堆中最后一个元素（数组最后一个元素）移动到堆顶位置。
     3. 移除最后一个元素（减小堆的大小）。
     4. 此时，新的堆顶元素可能违反堆属性。将其与其子节点比较（在最大堆中与较大的子节点比，在最小堆中与较小的子节点比），如果违反堆属性，则交换位置。这个过程（称为下沉 sift-down / bubble-down / sink）持续进行，直到该元素到达正确的位置（不再违反堆属性）或成为叶子节点。

   • 复杂度: O(log N)，因为最多需要沿着树的高度进行交换。

3. 获取堆顶元素 (Peek / Top):

   • 过程: 直接返回堆顶元素（数组的第一个元素），不修改堆。
   • 复杂度: O(1)。

4. 建堆 (Build Heap):

   • 过程: 给定一个无序数组，将其原地转换成一个满足堆属性的堆。
     • 方法一 (低效): 将数组元素逐个插入到一个空堆中，总复杂度 O(N log N)。
     • 方法二 (高效 - Floyd’s Algorithm): 从最后一个非叶子节点开始，向前遍历到根节点，对每个节点执行下沉 (sift-down) 操作。
       • 最后一个非叶子节点的下标约为 n/2 - 1 (对于0基数组)。
       • 这个方法被称为自底向上的堆化 (bottom-up heapify)。
   • 复杂度 (方法二): O(N)。虽然看起来是 N 次 sift-down (每次 O(log N))，但精确分析表明，大部分节点的下沉路径很短，总复杂度是线性的 O(N)。

优点:

• 高效获取最大/最小值 (O(1))。
• 高效插入和删除最大/最小值 (O(log N))。
• 构建堆的效率高 (O(N))。
• 空间效率高，使用数组存储，无需额外指针开销，缓存友好。

缺点:

• 查找任意元素效率低 (O(N))，因为除了堆顶元素外，其他元素没有严格的排序关系。
• 不适合需要频繁查找、删除任意元素或进行范围查询的场景。

主要应用:

1. 优先队列 (Priority Queue): 堆是实现优先队列最常用、最高效的数据结构。任务调度、事件模拟等场景广泛使用。
2. 堆排序 (Heap Sort): 一种原地、不稳定的排序算法。先将数组原地建成最大堆 (O(N))，然后 N-1 次将堆顶元素（当前最大值）与堆末尾元素交换，并缩小堆的大小，再对新的堆顶执行下沉操作 (N-1 次 * O(log N))。总复杂度 O(N log N)。
3. 求解 Top K 问题: 找到 N 个元素中最大（或最小）的 K 个。可以用一个大小为 K 的最小堆（找 Top K 大）或最大堆（找 Top K 小）来解决。遍历 N 个元素，维护堆的大小和属性。复杂度 O(N log K)。
4. 图算法: 如 Dijkstra 算法（最短路径）和 Prim 算法（最小生成树）中，使用最小优先队列（通常用最小堆实现）来高效地选取下一个要处理的顶点。
5. 动态中位数查找: 使用一个最大堆和一个最小堆组合来高效地找到数据流的中位数。

前缀树

核心概念与特点:

1. 结构性:

   • 完全二叉树: 堆通常用完全二叉树来实现。这意味着树的所有层级都是满的，除了可能的最后一层，最后一层的节点都尽量靠左排列。
   • 数组表示: 由于完全二叉树的特性，堆非常适合用**数组（或列表/向量）**来高效地存储，无需使用指针。父节点和子节点之间的关系可以通过数组下标的计算直接得出：
     • 对于下标为 i 的节点 (假设从 0 开始计数):
       • 父节点下标: floor((i - 1) / 2)
       • 左子节点下标: 2 * i + 1
       • 右子节点下标: 2 * i + 2
     • (如果从 1 开始计数，则父节点是 floor(i / 2), 左子节点 2_i, 右子节点 2_i + 1)

2. 堆属性 (Heap Property):

   • 这是堆的核心规则，决定了节点值与其子节点值之间的关系。根据这个属性，堆分为两种主要类型：
     • 最大堆 (Max-Heap): 父节点的值 大于或等于 (>=) 其所有子节点的值。这意味着堆顶（根节点）存储的是整个堆中的最大值。
     • 最小堆 (Min-Heap): 父节点的值 小于或等于 (<=) 其所有子节点的值。这意味着堆顶（根节点）存储的是整个堆中的最小值。
   • 注意: 堆属性只规定了父子关系，兄弟节点之间没有确定的大小关系。所以堆不是完全排序的结构。

主要操作:

堆的核心价值在于能够高效地执行以下操作：

1. 插入 (Insert / Add):

   • 过程: 将新元素添加到堆的末尾（数组的末尾），以保持完全二叉树的结构。然后，将这个新元素与其父节点比较，如果违反了堆属性（例如，在最大堆中新元素比父节点大），则交换它们的位置。这个过程（称为上浮 sift-up / bubble-up / swim）持续进行，直到新元素到达正确的位置（不再违反堆属性）或到达堆顶。
   • 复杂度: O(log N)，因为最多需要沿着树的高度进行交换。

2. 删除堆顶元素 (Extract-Max / Extract-Min):

   • 过程: 堆顶元素（最大值或最小值）是最常被需要或删除的。

     1. 保存堆顶元素的值（用于返回）。
     2. 将堆中最后一个元素（数组最后一个元素）移动到堆顶位置。
     3. 移除最后一个元素（减小堆的大小）。
     4. 此时，新的堆顶元素可能违反堆属性。将其与其子节点比较（在最大堆中与较大的子节点比，在最小堆中与较小的子节点比），如果违反堆属性，则交换位置。这个过程（称为下沉 sift-down / bubble-down / sink）持续进行，直到该元素到达正确的位置（不再违反堆属性）或成为叶子节点。

   • 复杂度: O(log N)，因为最多需要沿着树的高度进行交换。

3. 获取堆顶元素 (Peek / Top):

   • 过程: 直接返回堆顶元素（数组的第一个元素），不修改堆。
   • 复杂度: O(1)。

4. 建堆 (Build Heap):

   • 过程: 给定一个无序数组，将其原地转换成一个满足堆属性的堆。
     • 方法一 (低效): 将数组元素逐个插入到一个空堆中，总复杂度 O(N log N)。
     • 方法二 (高效 - Floyd’s Algorithm): 从最后一个非叶子节点开始，向前遍历到根节点，对每个节点执行下沉 (sift-down) 操作。
       • 最后一个非叶子节点的下标约为 n/2 - 1 (对于0基数组)。
       • 这个方法被称为自底向上的堆化 (bottom-up heapify)。
   • 复杂度 (方法二): O(N)。虽然看起来是 N 次 sift-down (每次 O(log N))，但精确分析表明，大部分节点的下沉路径很短，总复杂度是线性的 O(N)。

优点:

• 高效获取最大/最小值 (O(1))。
• 高效插入和删除最大/最小值 (O(log N))。
• 构建堆的效率高 (O(N))。
• 空间效率高，使用数组存储，无需额外指针开销，缓存友好。

缺点:

• 查找任意元素效率低 (O(N))，因为除了堆顶元素外，其他元素没有严格的排序关系。
• 不适合需要频繁查找、删除任意元素或进行范围查询的场景。

主要应用:

1. 优先队列 (Priority Queue): 堆是实现优先队列最常用、最高效的数据结构。任务调度、事件模拟等场景广泛使用。
2. 堆排序 (Heap Sort): 一种原地、不稳定的排序算法。先将数组原地建成最大堆 (O(N))，然后 N-1 次将堆顶元素（当前最大值）与堆末尾元素交换，并缩小堆的大小，再对新的堆顶执行下沉操作 (N-1 次 * O(log N))。总复杂度 O(N log N)。
3. 求解 Top K 问题: 找到 N 个元素中最大（或最小）的 K 个。可以用一个大小为 K 的最小堆（找 Top K 大）或最大堆（找 Top K 小）来解决。遍历 N 个元素，维护堆的大小和属性。复杂度 O(N log K)。
4. 图算法: 如 Dijkstra 算法（最短路径）和 Prim 算法（最小生成树）中，使用最小优先队列（通常用最小堆实现）来高效地选取下一个要处理的顶点。
5. 动态中位数查找: 使用一个最大堆和一个最小堆组合来高效地找到数据流的中位数。

布隆过滤器

核心思想:

布隆过滤器是一种空间效率极高的概率型数据结构，它用于判断一个元素是否可能存在于一个集合中。

• “可能存在”: 如果布隆过滤器判断元素存在，那么它可能真的存在，也可能是误判（False Positive）。
• “绝对不存在”: 如果布隆过滤器判断元素不存在，那么它一定不存在（No False Negatives）。

工作原理:

布隆过滤器主要由两部分组成：

1. 一个位数组（Bit Array）: 一个长度为 m 的位数组，所有位初始都为 0。
2. k 个独立的哈希函数（Hash Functions）: 这些哈希函数可以将输入元素均匀地映射到位数组的索引范围（0 到 m-1）内。

操作过程:

1. 添加元素 (Add):

   • 当你要向集合中添加一个元素 x 时：
   • 使用 k 个哈希函数分别对元素 x 进行计算，得到 k 个哈希值。
   • 将这 k 个哈希值（通常会对 m 取模）作为位数组的索引。
   • 将位数组中对应这 k 个索引位置的位（bit）都设置为 1。 （如果某个位已经是 1，则保持不变）。

2. 查询元素 (Query / Contains):

   • 当你要查询一个元素 y 是否在集合中时：
   • 同样使用那 k 个哈希函数分别对元素 y 进行计算，得到 k 个哈希值（索引）。
   • 检查位数组中对应这 k 个索引位置的位。
   • 判断逻辑:
     • 如果这 k 个位置上的位全部都是 1: 那么布隆过滤器会判断元素 y 可能存在于集合中。
     • 如果这 k 个位置中至少有一个位是 0: 那么布隆过滤器会判断元素 y 绝对不存在于集合中。

为什么会有误判 (False Positive)？

误判发生是因为多个不同的元素可能通过哈希函数映射到相同的位索引上。

假设元素 x 被添加到了过滤器中，它将 k 个位设置为了 1。现在查询一个从未添加过的元素 y。如果 y 经过 k 个哈希函数计算得到的 k 个索引位置，恰好都被其他已添加元素（可能是 x，也可能是别的元素）设置成了 1，那么过滤器在查询 y 时会发现所有对应位都是 1，从而错误地判断 y “可能存在”。

为什么没有漏判 (No False Negative)？

如果一个元素 x 确实被添加到了过滤器中，那么它对应的 k 个位一定都被设置成了 1。在查询 x 时，检查这 k 个位，必然会发现它们都是 1。因此，过滤器绝不会错误地判断一个实际存在的元素为“不存在”。

关键特性总结:

• 空间效率高: 不需要存储元素本身，只需要存储位数组，占用空间远小于存储实际元素。
• 查询和添加速度快: 时间复杂度主要取决于哈希函数的计算次数 k，通常认为是 O(k)，与集合中元素数量无关。
• 存在误判率 (False Positive Rate): 可以通过调整位数组大小 m 和哈希函数个数 k 来控制误判率。m 越大，k 选择得当，误判率越低，但空间和计算开销会增加。
• 没有漏判 (No False Negatives): 这是布隆过滤器最有价值的特性之一。
• 不支持删除操作 (标准实现): 删除一个元素需要将对应的 k 个位设为 0，但这可能会影响其他共享这些位的元素，导致漏判。有变种如计数布隆过滤器（Counting Bloom Filter）支持删除，但会牺牲一些空间效率。

应用场景:

布隆过滤器适用于那些可以容忍一定误判率，但对漏判零容忍，并且希望节省存储空间或提高查询速度的场景。例如：

• 网页爬虫: 判断一个 URL 是否已经被爬取过，避免重复爬取。
• 缓存系统: 判断一个请求的数据是否不在缓存中（如果判断不存在，则肯定不在，可以直接去数据库查；如果判断可能存在，再实际去查缓存）。这可以过滤掉大量无效的缓存查询。
• 数据库: 防止缓存穿透，快速判断一个 Key 是否不存在于数据库中。
• 垃圾邮件过滤: 判断发件人邮箱或 IP 是否在黑名单中。
• 推荐系统: 过滤掉用户已经看过的物品。

LRU

LRU（Least Recently Used，最近最少使用）缓存淘汰算法\

核心思想:

LRU 算法的核心思想是基于这样一个假设：如果一个数据在最近一段时间被访问过，那么它在将来被访问的可能性也更高；相反，如果一个数据在很长一段时间内都没有被访问过，那么它在将来被访问的可能性就比较低。

因此，当缓存空间已满，需要淘汰一些数据来腾出空间给新数据时，LRU 算法会选择淘汰掉最长时间没有被访问过的数据。

工作原理:

为了实现 LRU，缓存系统需要能够追踪每个缓存项的访问历史，特别是它们最后一次被访问的时间。当需要淘汰数据时，系统会找到那个“最后访问时间”距离现在最远的缓存项，并将其移除。

具体操作如下：

1. 数据访问 (Get):

   • 当需要访问某个数据时，首先检查它是否存在于缓存中。
   • 如果存在 (Cache Hit):
     • 获取该数据。
     • 关键操作： 将这个数据标记为“最近被访问过”（即更新其在访问顺序中的位置，使其成为最新的）。
   • 如果不存在 (Cache Miss):
     • 从数据源（如数据库、磁盘）获取数据。
     • 将这个新数据添加到缓存中，并标记为“最近被访问过”。
     • 检查缓存是否已满：
       • 如果缓存未满，直接添加。
       • 如果缓存已满，则需要先执行淘汰操作。

2. 数据添加 (Put / Cache Full Handling):

   • 当需要向缓存中添加一个新数据，或者因为 Cache Miss 需要添加数据时：
   • 检查缓存是否已满：
     • 如果未满： 将新数据添加到缓存，并将其标记为“最近被访问过”。
     • 如果已满：
       • 关键操作： 找到缓存中“最长时间未被访问”的数据（也就是处于访问顺序最末尾的数据）。
       • 将这个最久未使用的数据从缓存中淘汰（移除）。
       • 将新数据添加到缓存，并将其标记为“最近被访问过”。

常见实现方式:

最经典且高效的 LRU 实现方式是结合使用 哈希表（Hash Map / Dictionary） 和 双向链表（Doubly Linked List）：

1. 双向链表 (Doubly Linked List):

   • 用于维护缓存项的访问顺序。
   • 链表的节点存储缓存的 key 和 value (或者只存储 key，value 在哈希表中)。
   • 链表头部 (Head): 存放最近访问的元素。
   • 链表尾部 (Tail): 存放最久未访问的元素。
   • 操作:
     • 当一个元素被访问时，将其对应的链表节点移动到链表头部 (O(1) 时间复杂度)。
     • 当需要添加新元素时，将其添加到链表头部 (O(1) 时间复杂度)。
     • 当缓存已满需要淘汰时，移除链表尾部的节点 (O(1) 时间复杂度)。

2. 哈希表 (Hash Map):

   • 用于快速查找缓存项。
   • Key: 缓存项的键 (key)。
   • Value: 指向该键在双向链表中对应节点的指针或引用。
   • 操作:
     • 通过 Key 可以在 O(1) 的平均时间复杂度内找到链表中的节点。

结合工作流程:

• Get(key):

  1. 通过哈希表查找 key，得到对应的链表节点 (O(1))。

  2. 如果节点存在：

     • 将该节点从其当前位置移动到链表头部 (O(1))。
     • 返回节点中的 value。

  3. 如果节点不存在：返回 null 或表示未命中的值。

• Put(key, value):

  1. 通过哈希表查找 key (O(1))。

  2. 如果 key 已存在：

     • 更新节点中的 value。
     • 将该节点移动到链表头部 (O(1))。

  3. 如果 key 不存在：

     • 创建一个新的链表节点，包含 key 和 value。
     • 检查缓存是否已满 (通过比较当前大小和容量)。
     • 如果已满：
       • 获取链表尾部的节点 (最久未使用的)。
       • 从哈希表中移除尾部节点的 key (O(1))。
       • 从链表中移除尾部节点 (O(1))。
     • 将新节点添加到链表头部 (O(1))。
     • 将新节点的 key 和指向该节点的引用存入哈希表 (O(1))。

优点:

• 实现简单: 相对于一些更复杂的算法，LRU 的逻辑比较直观。
• 性能高效: 使用哈希表+双向链表的实现，get 和 put 操作的平均时间复杂度都是 O(1)。
• 命中率较好: 在大多数实际应用场景中，LRU 能提供不错的缓存命中率，因为它很好地利用了程序访问的“时间局部性”原理。

缺点:

• 需要额外的数据结构: 需要维护链表和哈希表，有一定的内存开销（特别是链表指针）。
• “缓存污染”问题: 对于偶然的、周期性的批量数据访问（例如全表扫描），LRU 表现不佳。这些仅仅被访问一次的“冷”数据会冲刷掉缓存中原本经常被访问的“热”数据，导致缓存命中率急剧下降。之后需要一段时间才能重新将热数据加载回缓存。